package list;

public class leetcode142 {
    public static void main(String[] args) {
        int[] nums = {3,2,0,-4};
        int pos = 1;
        ListNode head = createList(nums, pos);
        printList(head, nums);
        ListNode start = detectCycle(head);
        System.out.println("Start at:" + start.val);
    }

    public static ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                slow = head;
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    public static ListNode createList(int[] nums, int pos){
        ListNode head = new ListNode(nums[0]);
        ListNode temp = head;

        for (int i = 1; i < nums.length; i++) {
            ListNode cur = new ListNode(nums[i]);
            cur.next = null;
            temp.next = cur;
            temp = temp.next;
        }

        ListNode cur = head;

        while(pos >= 0){
            if(pos == 0)
                temp.next = cur;
            pos--;
            cur = cur.next;
        }

        return head;
    }

    public static void printList(ListNode head, int[] nums) {
        for(int i = 0; i < nums.length; i++){
            System.out.print(head.val + "->");
            head = head.next;
        }
        if(head == null) System.out.println("null");
        else {
            System.out.println(head.val + "-> null");
        }
    }

    public static boolean hasCycle(ListNode head){
        if(head == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        if(head.next == null) return false;
        while (fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return true;
        }
        return false;
    }
}
